#ifndef _SPARSE_MAP_WRAPPER_H_
#define _SPARSE_MAP_WRAPPER_H_

#include SPARSEHASHMAP_H
#include <algorithm>
using STL_NAMESPACE::pair;

_START_GOOGLE_NAMESPACE_

template <class Key, class T,
class HashFcn = SPARSEHASH_HASH<Key>,   // defined in sparseconfig.h
class EqualKey = STL_NAMESPACE::equal_to<Key>,
class Alloc = libc_allocator_with_realloc<pair<const Key, T> > >
class SparseMapWrapper
{
private:
	typedef sparse_hash_map<Key, T, HashFcn, EqualKey, Alloc> hm;
public:
	typedef typename hm::key_type key_type;
	typedef T data_type;
	typedef T mapped_type;
	typedef typename hm::value_type value_type;
	typedef typename hm::hasher hasher;
	typedef typename hm::key_equal key_equal;
	typedef Alloc allocator_type;

	typedef typename hm::size_type size_type;
	typedef typename hm::difference_type difference_type;
	typedef typename hm::pointer pointer;
	typedef typename hm::const_pointer const_pointer;
	typedef typename hm::reference reference;
	typedef typename hm::const_reference const_reference;

	typedef typename hm::iterator inner_iterator;
	typedef typename hm::const_iterator inner_const_iterator;
	//typedef typename hm::local_iterator local_iterator;
	//typedef typename hm::const_local_iterator const_local_iterator;

	class iterator {
		friend class SparseMapWrapper;
	private:
		SparseMapWrapper* innerMap;
		bool deletedKeyVisited;
		inner_iterator pos;
		inner_iterator end;
	public:
		iterator() {} // only used for declaration
		iterator(SparseMapWrapper* sparsemap, bool visitDeletedKey, inner_iterator it, inner_iterator it_end): innerMap(sparsemap),
			deletedKeyVisited(!visitDeletedKey), pos(it), end(it_end) {
				if (!innerMap->m_deletedKeyInserted) {
					deletedKeyVisited = true;
				}
		}
		// The default destructor is fine; we don't define one
		// The default operator= is fine; we don't define one

		// Happy dereferencer
		reference operator*() const
		{
			if (!deletedKeyVisited)
			{
				return *(innerMap->m_deletedKeyValue);
			}
			return *pos; 
		}
		pointer operator->() const { return &(operator*()); }

		// Arithmetic.
		iterator& operator++()   
		{
			if (!deletedKeyVisited)
			{
				deletedKeyVisited = true;
				return *this;
			}
			assert(pos != end); ++pos; return *this;
		}
		iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }

		// Comparison.
		bool operator==(const iterator& it) const { return deletedKeyVisited == it.deletedKeyVisited && pos == it.pos; }
		bool operator!=(const iterator& it) const { return deletedKeyVisited != it.deletedKeyVisited || pos != it.pos; }
	};

	class const_iterator {
		friend class SparseMapWrapper;
	private:
		SparseMapWrapper* innerMap;
		bool deletedKeyVisited;
		inner_const_iterator pos;
		inner_const_iterator end;
	public:
		const_iterator() {} // only used for declaration
		const_iterator(SparseMapWrapper* sparsemap, bool visitDeletedKey, inner_const_iterator it, inner_const_iterator it_end): innerMap(sparsemap),
			deletedKeyVisited(!visitDeletedKey), pos(it), end(it_end) {
				if (!innerMap->m_deletedKeyInserted) {
					deletedKeyVisited = true;
				}
		}
		const_iterator(const iterator &it) : innerMap(it.innerMap), deletedKeyVisited(it.deletedKeyVisited), pos(it.pos), end(it.end) { }
		// The default destructor is fine; we don't define one
		// The default operator= is fine; we don't define one

		// Happy dereferencer
		reference operator*() const
		{
			if (!deletedKeyVisited)
			{
				return innerMap->m_deletedKeyValue;
			}
			return *pos; 
		}
		pointer operator->() const { return &(operator*()); }

		// Arithmetic.
		const_iterator& operator++()   
		{
			if (!deletedKeyVisited)
			{
				deletedKeyVisited = true;
				return *this;
			}
			assert(pos != end); ++pos; return *this;
		}
		const_iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }

		// Comparison.
		bool operator==(const const_iterator& it) const { return deletedKeyVisited == it.deletedKeyVisited && pos == it.pos; }
		bool operator!=(const const_iterator& it) const { return deletedKeyVisited != it.deletedKeyVisited || pos != it.pos; }
	};

	// Iterator functions
	iterator begin()                               { return iterator(this, true, m_innerMap.begin(),	m_innerMap.end()); }
	iterator end()                                 { return iterator(this, false, m_innerMap.end(),	m_innerMap.end()); }
	const_iterator begin() const                   { return const_iterator(this, true, m_innerMap.begin(),	m_innerMap.end()); }
	const_iterator end() const                     { return const_iterator(this, false, m_innerMap.end(),	m_innerMap.end()); }

	explicit SparseMapWrapper(size_type expected_max_items_in_table = 0,
		const hasher& hf = hasher(),
		const key_equal& eql = key_equal(),
		const allocator_type& alloc = allocator_type()): m_innerMap(expected_max_items_in_table,
			hf, eql, alloc), m_isDeletedKeySet(false), m_deletedKeyInserted(false), m_deletedKeyValue(NULL)
	{
		set_deleted_key(key_type());
	}

	~SparseMapWrapper()
	{
		if (m_deletedKeyValue != NULL)
		{
			delete m_deletedKeyValue;
		}
	}

	void clear()                        { 
		m_deletedKeyInserted = false;
		if (m_deletedKeyValue) {
			delete m_deletedKeyValue;
			m_deletedKeyValue = NULL;
		}
		m_innerMap.clear();
	}

	void swap(SparseMapWrapper& hs)      {
		swap(m_isDeletedKeySet, hs.m_isDeletedKeySet);
		swap(m_deletedKeyValue, hs.m_deletedKeyValue);
		swap(m_deletedKeyInserted, hs.m_isDeletedKeySet);
		m_innerMap.swap(hs.m_innerMap);
	}

	// Functions concerning size
	size_type size() const              { return m_innerMap.size() + (m_deletedKeyInserted ? 1 : 0); }
	size_type max_size() const          { return m_innerMap.max_size(); }
	bool empty() const                  { return m_innerMap.empty() && !m_deletedKeyInserted; }

	void resize(size_type hint)         { m_innerMap.resize(hint); }
	void rehash(size_type hint)         { resize(hint); }      // the tr1 name

	// Lookup routines
	iterator find(const key_type& key)                 {
		if (m_isDeletedKeySet
			&& m_innerMap.hash_funct()(key) == m_innerMap.hash_funct()(m_innerMap.deleted_key())
			&& m_innerMap.key_eq()(key, m_innerMap.deleted_key())) {
			if (m_deletedKeyInserted) {
				return begin();
			}
			return end();
		}
		return iterator(this, false, m_innerMap.find(key),	m_innerMap.end());
	}

	const_iterator find(const key_type& key) const     {
		if (m_isDeletedKeySet
			&& m_innerMap.hash_funct()(key) == m_innerMap.hash_funct()(m_innerMap.deleted_key())
			&& m_innerMap.key_eq()(key, m_innerMap.deleted_key())) {
			if (m_deletedKeyInserted) {
				return begin();
			}
			return end();
		}
		return const_iterator(this, false, m_innerMap.find(key), m_innerMap.end());
	}

	data_type& operator[](const key_type& key) {       // This is our value-add!
		// If key is in the hashtable, returns find(key)->second,
		// otherwise returns insert(value_type(key, T()).first->second.
		// Note it does not create an empty T unless the find fails.
		if (m_isDeletedKeySet
			&& m_innerMap.hash_funct()(key) == m_innerMap.hash_funct()(m_innerMap.deleted_key())
			&& m_innerMap.key_eq()(key, m_innerMap.deleted_key())) {
				if (m_deletedKeyInserted) {
					return m_deletedKeyValue->second;
				}
				data_type default_data;
				m_deletedKeyValue = new value_type(key, default_data);
				m_deletedKeyInserted = true;
				return m_deletedKeyValue->second;
		}
		return m_innerMap[key];
	}

	size_type count(const key_type& key) const         {
		if (m_isDeletedKeySet
			&& m_innerMap.hash_funct()(key) == m_innerMap.hash_funct()(m_innerMap.deleted_key())
			&& m_innerMap.key_eq()(key, m_innerMap.deleted_key())) {
			if (m_deletedKeyInserted) {
				return 1;
			}
			return 0;
		}
		return m_innerMap.count(key); 
	}

	// Insertion routines
	pair<iterator, bool> insert(const value_type& obj)
	{
		if (m_isDeletedKeySet
			&& m_innerMap.hash_funct()(obj.first) == m_innerMap.hash_funct()(m_innerMap.deleted_key())
			&& m_innerMap.key_eq()(obj.first, m_innerMap.deleted_key()))
		{
			if (m_deletedKeyInserted) {
				return pair<iterator, bool>(begin(), false);
			}
			m_deletedKeyInserted = true;
			m_deletedKeyValue = new value_type(obj);
			return pair<iterator, bool>(begin(), true);
		}
		pair<inner_iterator, bool> ret = m_innerMap.insert(obj);
		return pair<iterator, bool>( iterator(this, false, ret.first, m_innerMap.end()), ret.second );
	}

	// required for std::insert_iterator; the passed-in iterator is ignored
	iterator insert(iterator, const value_type& obj)   { return insert(obj).first; }

private:
	// Deletion routines
	// THESE ARE NON-STANDARD!  I make you specify an "impossible" key
	// value to identify deleted buckets.  You can change the key as
	// time goes on, or get rid of it entirely to be insert-only.
	void set_deleted_key(const key_type& key)
	{
		m_innerMap.set_deleted_key(key);
		m_isDeletedKeySet = true;
	}

	void clear_deleted_key()                    {
		if (m_deletedKeyInserted)
			return;
		m_innerMap.clear_deleted_key();
		m_isDeletedKeySet = false;
	}

	key_type deleted_key() const                {
		return m_innerMap.deleted_key();
	}

public:
	// These are standard
	size_type erase(const key_type& key)               {
		if (m_isDeletedKeySet
			&& m_innerMap.hash_funct()(key) == m_innerMap.hash_funct()(m_innerMap.deleted_key())
			&& m_innerMap.key_eq()(key, m_innerMap.deleted_key()))
		{
			if (m_deletedKeyInserted) {
				m_deletedKeyInserted = false;
				delete m_deletedKeyValue;
				m_deletedKeyValue = NULL;
				return 1;
			}
			return 0;
		}
		return m_innerMap.erase(key); 
	}

	void erase(iterator it)                            {
		if (!it.deletedKeyVisited)
		{
			erase(m_deletedKeyValue->first);
			return;
		}
		m_innerMap.erase(it.pos);
	}
	void erase(iterator f, iterator l)                 {
		if (f == l) { return; }
		if (!f.deletedKeyVisited)
		{
			erase(f++);
		}
		m_innerMap.erase(f.pos, l.pos);
	}

	// Comparison
	bool operator==(const SparseMapWrapper& hs) const   { return m_isDeletedKeySet == hs.m_isDeletedKeySet
		&& m_deletedKeyInserted == hs.m_deletedKeyInserted && m_deletedKeyValue == hs.m_deletedKeyValue
		&& m_innerMap == hs.m_innerMap; }
	bool operator!=(const SparseMapWrapper& hs) const   { return m_isDeletedKeySet != hs.m_isDeletedKeySet
		|| m_deletedKeyInserted != hs.m_deletedKeyInserted || m_deletedKeyValue != hs.m_deletedKeyValue
		|| m_innerMap != hs.m_innerMap; }

	// I/O -- this is an add-on for writing metainformation to disk
	bool write_metadata(FILE *fp)
	{
		if (!fwrite(&m_isDeletedKeySet, sizeof(bool), 1, fp)
			|| !fwrite(&m_deletedKeyInserted, sizeof(bool), 1, fp)) {
			return false;
		}
		return m_innerMap.write_metadata(fp);
	}

	bool read_metadata(FILE *fp)
	{ 
		if (!fread(&m_isDeletedKeySet, sizeof(bool), 1, fp) //need reinterpret_cast<void*>?
			|| !fread(&m_deletedKeyInserted, sizeof(bool), 1, fp)) {
				return false;
		}
		if (m_deletedKeyInserted) {
			m_deletedKeyValue = new value_type;
		}
		return m_innerMap.read_metadata(fp); 
	}

	bool write_nopointer_data(FILE *fp)
	{
		if (m_deletedKeyInserted) {
			if (!fwrite(&(m_deletedKeyValue->first), sizeof(key_type), 1, fp) ||
				!fwrite(&(m_deletedKeyValue->second), sizeof(data_type), 1, fp)) {
					return false;
			}
		}
		return m_innerMap.write_nopointer_data(fp);
	}

	bool read_nopointer_data(FILE *fp)
	{ 
		if (m_deletedKeyInserted) {
			if (!fread(const_cast<key_type*>(&(m_deletedKeyValue->first)), sizeof(key_type), 1, fp) ||
				!fread(&(m_deletedKeyValue->second), sizeof(data_type), 1, fp)) {
					return false;
			}
		}
		if (m_innerMap.read_nopointer_data(fp)) {
			m_innerMap.set_deleted_key(m_deletedKeyValue->first);
			return true;
		}
		return false;
	}

private:
	hm m_innerMap;
	value_type* m_deletedKeyValue; ///< deleted key value pair
	bool m_deletedKeyInserted;
	bool m_isDeletedKeySet;
};

// We need a global swap as well
template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
inline void swap(SparseMapWrapper<Key, T, HashFcn, EqualKey, Alloc>& hm1,
				 SparseMapWrapper<Key, T, HashFcn, EqualKey, Alloc>& hm2) {
					 hm1.swap(hm2);
}

_END_GOOGLE_NAMESPACE_

#endif
